package com.crab.c05sorting;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 快速排序 分治法
 * 双边循环递归实现
 * 单边循环递归实现
 *
 * @author zfd
 * @version v1.0
 * @date 2022/4/29 15:38
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{4, 5, 7, 5, 1, 2, 9, 6};
        sortDouble(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

        arr = new int[]{4, 5, 7, 5, 1, 2, 9, 6};
        sortSingle(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

        arr = new int[]{4, 5, 7, 5, 1, 2, 9, 6};
        sortStack(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 双边循环递归实现
     *
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    public static void sortDouble(int[] arr, int startIndex, int endIndex) {
        // 递归结束条件 starIndex 大于或等于endIndex
        if (startIndex >= endIndex) {
            return;
        }

        //得到基准元素的位置
        int pivotIndex = partitionDouble(arr, startIndex, endIndex);

        // 根据基准元素 分成2部分进行递归排序
        sortDouble(arr, startIndex, pivotIndex - 1);
        sortDouble(arr, pivotIndex + 1, endIndex);

    }

    /**
     * 单边快排
     *
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    public static void sortSingle(int[] arr, int startIndex, int endIndex) {

        // 递归结束条件 starIndex 大于或等于endIndex
        if (startIndex >= endIndex) {
            return;
        }

        //得到基准元素的位置
        int pivotIndex = partitionSingle(arr, startIndex, endIndex);

        // 根据基准元素 分成2部分进行递归排序
        sortDouble(arr, startIndex, pivotIndex - 1);
        sortDouble(arr, pivotIndex + 1, endIndex);

    }

    /**
     * 使用堆栈实现不用递归
     *
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    public static void sortStack(int[] arr, int startIndex, int endIndex) {
        //
        Stack<Map<String, Integer>> quickSortStack = new Stack<>();

        //
        HashMap<String, Integer> rootParam = new HashMap<>();
        rootParam.put("startIndex", startIndex);
        rootParam.put("endIndex", endIndex);
        quickSortStack.push(rootParam);

        // 循环结束条件： 栈为空
        while (!quickSortStack.isEmpty()) {
            Map<String, Integer> param = quickSortStack.pop();
            // 基准元素 单边循环
            int pivotIndex = partitionSingle(arr, param.get("startIndex"), param.get("endIndex"));
            // 根据基准元素分成2部分 将没部分的起止下标入栈
            // 左
            if (param.get("startIndex") < pivotIndex - 1) {
                Map<String, Integer> left = new HashMap<>();
                left.put("startIndex", param.get("startIndex"));
                left.put("endIndex", pivotIndex - 1);
                quickSortStack.push(left);
            }
            // 右
            if (param.get("endIndex") > pivotIndex + 1) {
                Map<String, Integer> right = new HashMap<>();
                right.put("startIndex", pivotIndex + 1);
                right.put("endIndex", param.get("endIndex"));
                quickSortStack.push(right);
            }
        }
    }


    /**
     * 分治法 单边循环
     *
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    private static int partitionSingle(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        int mark = startIndex;

        for (int i = startIndex + 1; i <= endIndex; i++) {
            // 小于基准值 mark右移，交换mark位置的元素和当前遍历的元素
            if (arr[i] < pivot) {
                mark++;
                int temp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = temp;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }


    /**
     * 分治法 双边循环
     *
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    private static int partitionDouble(int[] arr, int startIndex, int endIndex) {
        // 基准取第一个
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            // 控制right指针比较并左移
            while (left < right && arr[right] > pivot) {
                right--;
            }
            // 控制left 并右移
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 一轮完毕 交换left和right指针所指向的元素
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }

        // pivot和指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }
}
